#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 438. 找到字符串中所有字母异位词
class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int k = p.size(), m = s.size();
        int cnt1[26]{}, cnt2[26]{}, count = 0;
        for(char ch : p) ++cnt1[ch - 'a'];

        int left = 0, right = 0;
        vector<int> ret;
        while(right < m)
        {
            char in = s[right];
            if(++cnt2[in - 'a'] <= cnt1[in - 'a']) ++count;
            if(right - left + 1 > k)
            {
                char out = s[left++];
                if(cnt2[out - 'a']-- <= cnt1[out - 'a']) --count;
            }
            if(count == k) ret.push_back(left);
            ++right;
        }
        return ret;
    }
};

// 2156. 查找给定哈希值的子串
class Solution 
{
public:
    string subStrHash(string s, int pow, int mod, int k, int val) 
    {
        int n = s.size();
        long long hash = 0, p = 1;
        for(int i = n - 1; i >= n - k; --i)
        {
            hash = (hash * pow + (s[i] - 'a' + 1)) % mod;
            p = p * pow % mod;
        }

        int pos = 0;
        if(hash == val) pos = n - k;

        for(int i = n - k - 1; i >= 0; --i)
        {
            hash = (hash * pow + (s[i] - 'a' + 1) + mod - p * (s[i + k] - 'a' + 1) % mod) % mod;
            if(hash == val) pos = i;
        }
        return s.substr(pos, k);
    }
};

class Solution 
{
public:
    int numKLenSubstrNoRepeats(string s, int k) 
    {
        unordered_map<int, int> m;
        int ret = 0, left = 0, right = 0, n = s.size();
        while(right < n)
        {
            ++m[s[right]];
            if(right - left + 1 > k)
            {
                if(m[s[left]] == 1) m.erase(s[left]);
                else --m[s[left]];
                ++left;
            }
            if(right - left + 1 == k)
            {
                if(m.size() == k) ++ret;
            }
            ++right;
        }
        return ret;
    }
};

// 3. 无重复字符的最长子串
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int m[128]{}, left = 0, right = 0, ret = 0, n = s.size();
        while(right < n)
        {
            ++m[s[right]];
            while(m[s[right]] > 1)
            {
                --m[s[left++]];
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};

// 1493. 删掉一个元素以后全为 1 的最长子数组
class Solution 
{
public:
    int longestSubarray(vector<int>& nums) 
    {
        int left = 0, right = 0, n = nums.size(), ret = 0, zero = 0;
        while(right < n)
        {
            if(nums[right] == 0) ++zero;
            while(zero > 1)
            {
                if(nums[left] == 0) --zero;
                ++left;
            }
            if(zero == 0) ret = max(ret, right - left + 1);
            else ret = max(ret, right - left);
            ++right;
        }
        return ret == n ? n - 1 : ret;
    }
};

// 904. 水果成篮
class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        unordered_map<int, int> m;
        int left = 0, right = 0, ret = 0, n = fruits.size();
        while(right < n)
        {
            ++m[fruits[right]];
            while(m.size() > 2)
            {
                --m[fruits[left]];
                if(m[fruits[left]] == 0) m.erase(fruits[left]);
                ++left;
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};

// 1695. 删除子数组的最大得分
class Solution 
{
public:
    int maximumUniqueSubarray(vector<int>& nums) 
    {
        unordered_map<int, int> m;
        int left = 0, right = 0, n = nums.size(), sum = 0, ret = 0;
        while(right < n)
        {
            sum += nums[right];
            ++m[nums[right]];
            while(m[nums[right]] > 1)
            {
                --m[nums[left]];
                sum -= nums[left];
                if(m[nums[left]] == 0) m.erase(nums[left]);
                ++left;
            }
            ret = max(ret, sum);
            ++right;
        }
        return ret;
    }
};

// 2024. 考试的最大困扰度
class Solution 
{
public:
    int maxConsecutiveAnswers(string answerKey, int k) 
    {
        auto f = [&](char ch)
        {
            int left = 0, right = 0, n = answerKey.size(), ret = 0, count = 0;
            while(right < n)
            {
                if(answerKey[right] == ch) ++count;
                while(count > k)
                {
                    if(answerKey[left++] == ch) --count;
                }
                ret = max(ret, right - left + 1);
                ++right;
            }
            return ret;
        };

        return max(f('T'), f('F'));
    }
};

// 1208. 尽可能使字符串相等
class Solution 
{
public:
    int equalSubstring(string s, string t, int maxCost) 
    {
        int m = s.size(), left = 0, right = 0, ret = 0, cost = 0;
        while(right < m)
        {
            cost += abs(s[right] - t[right]);
            while(cost > maxCost)
            {
                cost -= abs(s[left] - t[left]);
                ++left;
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret;
    }
};

// 2831. 找出最长等值子数组
class Solution 
{
public:
    int longestEqualSubarray(vector<int>& nums, int k) 
    {
        int n = nums.size();    
        vector<vector<int>> pos(n + 1);
        for(int i = 0; i < n; ++i)
        {
            pos[nums[i]].push_back(i);
        }

        int ret = 0;
        for(auto& p : pos)
        {
            int left = 0;
            for(int right = 0; right < p.size(); ++right)
            {
                while(p[right] - p[left] + 1 - (right - left + 1) > k) ++left;
                ret = max(ret, right - left + 1);
            }
        }
        return ret;
    }
};

// 2106. 摘水果
class Solution 
{
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) 
    {
        int left = lower_bound(fruits.begin(), fruits.end(), startPos - k, [](const auto& a, int b){
            return a[0] < b;
        }) - fruits.begin();

        int sum = 0, n = fruits.size(), ret = 0;
        for(int right = left; right < n && fruits[right][0] <= startPos + k; ++right)
        {
            // 枚举最右位置为 fruits[right][0]
            sum += fruits[right][1];
            while(2 * fruits[right][0] - fruits[left][0] - startPos > k &&
                  fruits[right][0] + startPos - 2 * fruits[left][0] > k)
            {
                sum -= fruits[left++][1]; // fruits[left][0] 无法到达
            }
            ret = max(ret, sum);
        }
        return ret;
    }
};